package algotithm.jianzhioffer.test34;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/22-10:14
 */
public class Solution {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(11);
        TreeNode node5 = new TreeNode(13);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(2);
        TreeNode node9 = new TreeNode(5);
        TreeNode node10 = new TreeNode(1);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = null;
        node3.left = node5;
        node3.right = node6;
        node4.left = node7;
        node4.right = node8;
        node5.left = null;
        node5.right = null;
        node6.left = node9;
        node6.right = node10;
        node7.left = null;
        node7.right = null;
        node8.left = null;
        node8.right = null;
        node9.left = null;
        node9.right = null;
        node10.left = null;
        node10.right = null;

        Solution solution = new Solution();
        List<List<Integer>> res = solution.pathSum(node1, 22);
        for (List<Integer> list : res) {
            System.out.println(list);
        }
    }


    //    LinkedList<List<Integer>> res = new LinkedList<>();
//    LinkedList<Integer> path = new LinkedList<>();
//
//    public List<List<Integer>> pathSum(TreeNode root,int sum) {
//        recur(root,sum);
//        return res;
//    }
//
//    public void recur(TreeNode root,int tar) {
//        if (root == null) {
//            return;
//        }
//        path.add(root.val);
//        tar -= root.val;
//        if (tar == 0 && root.left == null && root.right == null) {
//            res.add(new LinkedList<>(path));
//        }
//        recur(root.left,tar);
//        recur(root.right,tar);
//        path.removeLast();
//    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        recur(root, sum, res, path);
        return res;
    }

    public void recur(TreeNode root, int sum, List<List<Integer>> res, LinkedList<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            res.add(new ArrayList<>(list));
        }
        recur(root.left, sum, res, list);
        recur(root.right, sum, res, list);
        list.removeLast();
    }
}
